package org.uc3m.ed.tad.arbol;

import java.util.LinkedList;

/**
 * Implementacion <B>no robusta</B> de un iterador para arbol binario. El
 * iterador permite recorrer los elementos del arbol en preorden, inorden o
 * postorden segun la decision del usuario.
 * 
 * @author DEI - ED
 * @version 1.0
 */

public class ArbolBinarioIterador<C extends Comparable<C>, E> implements
		IArbolBinarioIterador<C, E> {
	
	/**
	 * Posicion del arbol recorrido hasta el momento.
	 */
	int _actual;

	/**
	 * Datos contenidos en el arbol tras aplanarlo.
	 * 
	 * @see LinkedList<E>
	 */
	LinkedList<E> _contenido;

	/**
	 * Crea un iterador sobre un arbol. El arbol se recorre en inorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	public ArbolBinarioIterador(IArbolBinario<C, E> arbol) {
		_actual = 0;
		_contenido = new LinkedList<E>();
		
		aplanarInorden(arbol);
	}

	/**
	 * Crea un iterador sobre un arbol. El arbol respeta el recorrido indicado
	 * por parametro.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 * @param recorrido
	 *            Define el recorrido seguido por el iterador.
	 */
	public ArbolBinarioIterador(IArbolBinario<C, E> arbol, Recorrido recorrido) {
		_actual = 0;
		_contenido = new LinkedList<E>();		
		
		switch (recorrido) {
		case INORDEN:
			aplanarInorden(arbol);
			break;

		case PREORDEN:
			aplanarPreorden(arbol);
			break;

		case POSTORDEN:
			aplanarPostorden(arbol);
			break;
		}		
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.arbol.ArbolBinarioIterador#haySiguiente()
	 */
	public boolean haySiguiente() {
		return (_actual < _contenido.size());
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.arbol.ArbolBinarioIterador#siguiente()
	 */
	public E siguiente() {
		E siguiente = null;
		
		siguiente = _contenido.get(_actual);
		_actual++;

		return siguiente;
	}

	/**
	 * Inicializa el contenido de la pila para realizar el recorrido inorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	private void aplanarInorden(IArbolBinario<C, E> arbol) {
		if(arbol != null) {
			aplanarInorden(arbol.subarbolIzquierdo());
			_contenido.add(arbol.raiz());			
			aplanarInorden(arbol.subarbolDerecho());			
		}
	}

	/**
	 * Inicializa el contenido de la pila para realizar el recorrido preorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	private void aplanarPreorden(IArbolBinario<C, E> arbol) {
		if(arbol != null) {
			_contenido.add(arbol.raiz());					
			aplanarInorden(arbol.subarbolIzquierdo());	
			aplanarInorden(arbol.subarbolDerecho());	
		}	
	}

	/**
	 * Inicializa el contenido de la pila para realizar el recorrido postorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	private void aplanarPostorden(IArbolBinario<C, E> arbol) {
		if(arbol != null) {
			aplanarInorden(arbol.subarbolIzquierdo());
			aplanarInorden(arbol.subarbolDerecho());
			_contenido.add(arbol.raiz());		
		}	
	}

}
